//
// Created by francklinson on 2021/6/28.
//

//给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
//
//例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
//现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
//
//求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/bus-routes
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <vector>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

class Solution {
public:
    int numBusesToDestination(vector<vector<int>> &routes, int source, int target) {
        /**
         * BFS
         * 首先根据车辆路线图，知道在每一站坐车能够到达的下一站
         */
        if (source == target) return 0;
        // hash 储存每一站能到达的下一站 等于一个站牌
        unordered_map<int, unordered_set<int>> availNextStation;
        // 遍历车的路线
        for (auto &route:routes) {
            //遍历每一站
            for (auto &x:route) {
                for (auto &y:route) {
                    if (y != x)
                        availNextStation[x].insert(y);
                }
            }
        }
        // bfs队列 存当前站，坐了几辆车
        queue<pair<int, int>> q;
        // 从起始站开始
        q.emplace(source, 1);
        // 已经经过了哪几站
        unordered_set<int> passed;
        while (!q.empty()) {
            auto curStatus = q.front();
            q.pop();
            // 遍历能到的下一站
            for (auto &x:availNextStation[curStatus.first]) {
                // 到达终点
                if (x == target) return curStatus.second;
                //已经坐到过了
                if (passed.find(x) != passed.end()) continue;
                // 入队
                q.emplace(x, curStatus.second + 1);
                passed.insert(x);
            }
        }
        return -1;
        // 超时
    }
};

class Solution2 {
public:
    int numBusesToDestination(vector<vector<int>> &routes, int source, int target) {
        // 会有XX不上公交车...起点就是终点...
        if (source == target) { return 0; }
        // 先遍历所有的路线中的站台，把每个站台所能路过的车辆都记录下来
        unordered_map<int, vector<int> > stationToRoute;
        for (int i = 0; i < routes.size(); i++) {
            for (int j = 0; j < routes[i].size(); j++) {
                stationToRoute[routes[i][j]].push_back(i);
            }
        }
        // 再次遍历所有站台，根据站台经过的路线，来建立路线之间的关系
        // 得到每条线路的交集线路
        vector<vector<int> > routeToRoutes(500, vector<int>(0));
        for (auto &p : stationToRoute) {
            for (auto &route : p.second) {
                for (auto &secondRoute : p.second) {
                    if (secondRoute != route) {
                        routeToRoutes[route].push_back(secondRoute);
                    }
                }
            }
        }

        unordered_set<int> endRoutes;
        // 能够到达终点的线路
        for (auto &route : stationToRoute[target]) {
            endRoutes.insert(route);
        }

        vector<bool> visited(500, false);

        // 首先得有一个queue可以存档node和一些信息
        // <第几个route, 上过几辆车了>
        queue<pair<int, int> > q;
        // 初始站台能经过的车辆线路
        for (auto &route : stationToRoute[source]) {
            q.push({route, 0});
        }
        while (!q.empty()) {
            // 取出queue元素
            auto tmp = q.front();
            q.pop();
            // 如果访问过了，就continue;
            // 再设置一下visited
            if (visited[tmp.first]) {
                continue;
            }
            // 没访问过，就看看是不是终点
            visited[tmp.first] = true;
            // 发现了能够到达终点的线路
            if (endRoutes.find(tmp.first) != endRoutes.end()) {
                return tmp.second + 1;
            }
            for (auto &route : routeToRoutes[tmp.first]) {
                // 对于所所有下个可能，入queue
                if (!visited[route]) {
                    q.push({route, tmp.second + 1});
                }
            }
        }
        return -1;
    }
};


int main() {
    vector<vector<int>> routes{{1, 2, 7},
                               {3, 6, 7}};

    vector<vector<int>> routes2{{7,  12},
                                {4,  5,  15},
                                {6},
                                {15, 19},
                                {9,  12, 13}
    };
    Solution sol;
    cout << sol.numBusesToDestination(routes, 1, 6) << endl;
    cout << sol.numBusesToDestination(routes2, 4, 19) << endl;
    return 0;
}